The present invention relates to routing schemes in communication networks and, more particularly, to a courteous routing scheme.
Routing in a telecommunication network is a critical function that shapes the design and operation of the network. The routing function in circuit-switched and data networks has been extensively studied. In particular, routing schemes in circuit-switched networks, such as the public switched telephone network (PSTN), have been enhanced over the past few decades. However, circuit-switched networks are not, at present, undergoing any significant changes, and currently-employed routing schemes, such as classical hierarchical routing and the variety of flat-routing schemes including those known as adaptive routing, dynamic routing and high-performance routing, are likely to remain unchanged. Data networks, in contrast, are undergoing significant changes. In particular, the Internet has experienced very rapid growth in coverage and capacity. In addition to coverage and capacity expansion, it is now widely recognized that quality control is a major requirement for an effective global Internet. The manner in which quality-of-service (QoS) and grade-of-service (GoS) are controlled is determined primarily by schemes employed for routing and traffic allocation. A node controlling QoS or GoS should have an ability to allocate traffic loads among alternative outgoing routes.
A network may be modeled as comprising nodes that are fully or partially interconnected by (transmission) links, where the links may have different capacities and different associated costs. As well, the number of links emanating from each node may vary from one node to another. The term xe2x80x9cnodexe2x80x9d, as used herein, is used for a router or switch responsible for routing and traffic allocation. A route is a link or a chain of links connecting a source node to a sink node where a source node is the node supporting traffic sources (the origins of traffic) and a sink node is the node supporting traffic sinks (the destinations of traffic). A node functioning as a router determines a subjective xe2x80x9cbest routexe2x80x9d to another node based on various factors which may be combined to determine a cost factor. The factors may include qualities such as reliability and delay. A node may function as a source node and a sink node for distinct streams of traffic.
A source node and a sink node form a xe2x80x9cnode-pairxe2x80x9d. For a particular node-pair, each member of an associated xe2x80x9croute setxe2x80x9d is a different route between the source node and the sink node that comprise the node-pair. The routes within each route set may be selected to have different first links and may be ranked according to such criteria as total cost and route intersection levels. Conventionally, the route sets for different node-pairs are, however, determined independently without considering the level of intersection among routes connecting different sources to sinks.
Upon arrival of a connection request at a particular node, a controller of that particular node may allocate the requested connection to one of the routes in a route set associated with the node-pair comprising the particular node and the sink node specified by the connection request. In one routing scheme, the route to which the requested connection is allocated may be, for instance, the highest ranked route that has sufficient free capacity, where the routes of a route set are ranked by cost.
In many routing schemes, a particular route in a route set may further have an x associated xe2x80x9cstatic route capacityxe2x80x9d which is representative of the full capacity of the link in the route that has least capacity. By definition, the xe2x80x9cfull capacityxe2x80x9d of a link is the maximum data rate that can be supported by the link. The static route capacity of a particular route in a route set may be included in the same data structure that identifies the path of each route in the route set, or may otherwise be made available to a source node. However, the full capacity of one link in the particular route may not always be available to a source node considering allocation of a connection to the particular route.
Traffic allocated to routes in distinct route sets may compete for the capacities of common links. This results in two undesirable effects. The first is that a high proportion of connection attempts may fail to use the best route, leading to use of other routes in respective route sets for the node-pairs and increasing the required computational effort. The second is that haphazard redirection of a connection away from its best route may lead to a connection being allocated to a next best route in a meager route set (i.e., a route set with few members). Where one connection between a first node-pair has been allocated to a first route, the next best route in the meager route set of a second node-pair may be significantly more costly than the next best route in the route set for the first node-pair.
The routing scheme of the present invention is called xe2x80x9ccourteousxe2x80x9d because the node-pair that suffers the least by a diversion of a part of its traffic to a higher-cost route yields the use of a potentially overloaded link to node-pairs that suffer more by redirecting traffic. The method of the present invention involves providing nodes with route-adaptation information including a route set for each node-pair, and a load-adaptation vector to associate with each route set. A route set includes a number of alternate routes from a source node to a sink node and a load-adaptation vector influences the allocation of traffic to individual routes within the route set with which it is associated. The method uses a minimum-penalty criterion with minimum route-intersection to resolve conflicting objectives. The route-adaptation information may, periodically, be updated in response to a metric representative of traffic change exceeding a threshold.
In accordance with an aspect of the present invention there is provided, at a controller of a network, the network including nodes and links between the nodes, a method of distributing routing information to the nodes, the method including receiving traffic information from the nodes and, based on the received traffic information, determining adaptive routing information corresponding to each node. The method further includes transmitting to each node the corresponding adaptive routing information for use by each node in making traffic routing decisions. In a further aspect of the present invention, there is provided a software medium that permits a general purpose computer to carry out this method.
In accordance with a further aspect of the present invention there is provided, in a network including nodes interconnected by links, where each of the nodes has a route set corresponding to each other of the nodes in the network, and each route set comprises a set of routes to the each other of the nodes in the network, a method of route capacity allocation, including transmitting, to each of the nodes, node-specific adaptive routing information for use by each of the nodes in route capacity allocation, and receiving traffic information from the nodes. The method further includes, responsive to a determination that, based on the received traffic information and the node-specific adaptive routing information, traffic allocated to two or more routes having a common link may overload the common link, altering the node-specific adaptive routing information such that a proportion of traffic allocated to a given route of the two or more routes having the common link is re-directed to an alternate route where the given route is in a given route set in which a cost differential between the given route and the alternate route is a minimum. The method also includes transmitting the altered node-specific adaptive routing information to each of the nodes to which the altered node-specific adaptive routing information corresponds.
In accordance with a further aspect of the present invention there is provided, at a first node in a network, the network including nodes, links between the nodes and a controller, a method of allocating connection requests to routes, the method including receiving a load-adaptation vector, the load-adaptation vector corresponding to a route set including different routes between the first node and a second node in the network, each element in the load-adaptation vector corresponding to a unique route in the route set and having a value for influencing allocation of traffic to the unique route. The method also includes initializing a vacancy vector, receiving a request to connect the first node to the second node, the request having an associated load size and comparing an element in the vacancy vector to the load size. Where a given element in the vacancy vector exceeds or equals the load size, the method includes allocating the request to a route corresponding to the given element and reducing the available capacity indicated by the given element by the load size. In another aspect of the invention a node is provided for performing this method. In a further aspect of the present invention, there is provided a software medium that permits a general purpose computer to carry out this method.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.